﻿//435. 无重叠区间
//给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。



//贪心
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals)
    {
        if (intervals.empty()) {
            return 0;
        }

        sort(intervals.begin(), intervals.end(), [](const auto& u, const auto& v) {
            return u[0] < v[0];
            });
        int count = 0;
        int n = intervals.size();
        for (int i = 1; i < n; i++)
        {
            //判断是否与上一个区域重叠
            if (intervals[i][0] < intervals[i - 1][1])
            {
                count++;
                intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]);
            }
        }
        return count;
    }
};



//动态规划
class Solution 
{
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals)
    {
        if (intervals.empty()) {
            return 0;
        }

        sort(intervals.begin(), intervals.end(), [](const auto& u, const auto& v) {
            return u[0] < v[0];
            });

        int n = intervals.size();
        vector<int> dp(n, 1);

        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (intervals[j][1] <= intervals[i][0]) //不重叠
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return n - *max_element(dp.begin(), dp.end());
    }
};